package com.sort.animation;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class BiNodeFactory {

    private final static int W_SPAN = 120;
    private final  static int H_SPAN = 90;

    public static List<BiNode> createBiNodeSequence(int nums, int x, int y) {

        int values[] = new int[nums];
        for (int i = 0; i < nums; i++) {
            values[i] = i+1;
        }
        return createBiNode(values, x, y);
    }

    public static List<BiNode> createBiNodeRandom(int nums, int x, int y) {

        Random random = new Random();
        int values[] = new int[nums];
        for (int i = 0; i < nums; i++) {
            values[i] = random.nextInt(100);
        }
        return createBiNode(values, x, y);
    }

    public static int getHeight(int nums) {
        int h = 1;
        int count = 1;
        while ((h = (int) Math.pow(2, count) - 1) < nums) {
                    count ++;
        }
        return count ;
    }

    public static void main(String[] args) {

        System.out.println(getFullNumber(3));
        System.out.println(getFullNumber(5));
        System.out.println(getFullNumber(7));
        System.out.println(getFullNumber(8));
    }


    private static int getFullNumber(int nums){
        int sum = 1;
        int count = 1;
        while ((sum = (int) Math.pow(2, count) - 1) < nums) {
            count ++;
        }
        return sum;
    }



    public static List<BiNode> createBiNode(int[] values ,int x,int y){

        List<BiNode> biNodes = new ArrayList<>(values.length);

        int fullNum = getFullNumber(values.length);

        int[] xValues = new int[fullNum];
        int[] yValues = new int[fullNum];

        int level = getHeight(values.length) - 1;
        int levelElementNum = (int) Math.pow(2, level);
        int levelFirst = (int) Math.pow(2, level) - 1;
        for (int j = 0; j < levelElementNum / 2; j++) {

            int left = x - W_SPAN / 2 - j * W_SPAN;
            int right = x + W_SPAN / 2 + j * W_SPAN;

            int index1 = levelFirst + levelElementNum / 2 - 1 - j;
            int index2 = levelFirst + levelElementNum / 2 + j;

            if (index1 < fullNum) {
                xValues[index1] = left;
                yValues[index1] = y + H_SPAN * level;
            }

            if (index2 < fullNum) {
                xValues[index2] = right;
                yValues[index2] = y + H_SPAN * level;
            }
        }

        for (int i = levelFirst - 1; i >= 0; i--) {
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            xValues[i] = (xValues[left] + xValues[right]) / 2;
            yValues[i] = yValues[left] - H_SPAN;
        }


        for (int i = 0; i < values.length; i++) {
            BiNode biNode = new BiNode(values[i], xValues[i], yValues[i]);
            biNodes.add(biNode);
        }

        return biNodes;
    }



}
